package com.lw.leetcode.stack.b;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 739. 每日温度
 * 剑指 Offer II 038. 每日温度
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/9 9:38
 */
public class DailyTemperatures {

    public static void main(String[] args) {
        DailyTemperatures test = new DailyTemperatures();

        // [1,1,4,2,1,1,0,0]
        int[] arr = {73,74,75,71,69,72,76,73};

        int[] ints = test.dailyTemperatures(arr);
        System.out.println(Arrays.toString(arr));
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        Stack<Integer> vs = new Stack<>();
        Stack<Integer> is = new Stack<>();
        for (int i = length - 1; i >= 0; i--) {
            int v = temperatures[i];
            while (!vs.isEmpty() && v >= vs.peek()) {
                vs.pop();
                is.pop();
            }
            if (!vs.isEmpty()) {
                temperatures[i] = is.peek() - i;
            } else {
                temperatures[i] = 0;
            }
            vs.add(v);
            is.add(i);
        }
        return temperatures;
    }

    public int[] dailyTemperatures2(int[] temperatures) {
        int length = temperatures.length;
        int[] a = new int[length];
        int[] b = new int[length];
        int end = 1;
        for (int i = 1; i < length; i++) {
            int n = temperatures[i];
            int j;
            for (j = end - 1; j >= 0; j--) {
                if (temperatures[b[j]] < n) {
                    a[b[j]] = i - b[j];
                } else {
                    break;
                }
            }
            end = j + 2;
            b[end - 1] = i;
        }
        return a;
    }

}
